Multiplicative Group Of Integers Modulo \(n\)
The group \(\mathbb{U}_n = \mathbb{Z}_n^{\ast}\) denotes the multiplicative group of a ring of the ring \(\mathbb{Z}_n\).
Precisely which elements are in \(\mathbb{U}_n\) can be categorised by the following theorem:
Any non-zero element \(a \in \mathbb{Z}_n\) has a multiplicative inverse if and only if \(\mathrm{gcd}(a, n) = 1\).
Proof
This fact follows very naturally from the Bezout identity, specifically, consider that the equation
has a solution in \(x\) if and only if there exists an \(x, y\) solving the equivalent equation:
which occurs if and only \(\mathrm{gcd}(a, p) \mid 1\) which is equivalent to \(\mathrm{gcd}(a, p) = 1\).
This fact then gives the basis for determining when \(\mathbb{Z}_n\) is a field, that is the finite field of integers modulo \(p\).